def lower_bound(nums, target):
    """
    返回nums中第一个>=target的值的位置，如果nums中都比target小，则返回 len(nums)
    c++ 插入都是前插, 这样 target 刚好被插入合适的位置
    原文链接：https://blog.csdn.net/u010366748/article/details/52539151
    :param nums:
    :param target:
    :return:
    """
    low, high = 0, len(nums) - 1
    pos = len(nums)  # 初始化为 end() 位置
    while low < high:
        # low <= mid < high; 所以 mid + 1 <= high, 所以 low <= high
        # 终止条件是 low>= high, 所以终止时, low==high
        mid = (low + high) // 2
        if nums[mid] < target:
            low = mid + 1
        else:  # nums[mid] >= targe
            high = mid
            # pos = high
    # print(f'lower_bound, low, high: {(low, high)}')
    if nums[low] >= target:
        pos = low
    return pos


def upper_bound(nums, target):
    """
    返回nums中第一个 >target 的位置，如果 nums 都 <= target，则返回 len(nums)
    原文链接：https://blog.csdn.net/u010366748/article/details/52539151
    :param nums:
    :param target:
    :return:
    """
    low, high = 0, len(nums) - 1
    pos = len(nums)  # 初始化为 end() 位置
    while low < high:
        mid = (low + high) // 2
        if nums[mid] <= target:
            low = mid + 1
        else:  # nums[mid] > target
            high = mid
            # pos = high
    # print(f'upper_bound, low, high: {(low, high)}')
    if nums[low] > target:
        pos = low
    return pos


if __name__ == '__main__':
    nums = [10, 10, 10, 20, 20, 20, 30, 30]
    print(lower_bound(nums, 9))
    print(lower_bound(nums, 10))
    print(lower_bound(nums, 15))
    print(lower_bound(nums, 20))
    print(lower_bound(nums, 25))
    print(lower_bound(nums, 30))
    print(lower_bound(nums, 40))
    print('-------------------------')
    print(upper_bound(nums, 9))
    print(upper_bound(nums, 10))
    print(upper_bound(nums, 15))
    print(upper_bound(nums, 20))
    print(upper_bound(nums, 25))
    print(upper_bound(nums, 30))
    print(upper_bound(nums, 40))
